1. Field of the Invention
The present invention relates to routing devices for data transmission networks, and especially to routing devices having a capability to make decisions.
2. Description of the Related Art
Communication networks in which data is transferred from a source to a destination in packets, each packet being sent in a series of steps from one component in the network to the next until it reaches its destination, are well known. Some such networks attempt to deliver guarantees of bandwidth and specific limits on the delay that packets experience and the proportion of them that must be discarded during periods of congestion.
One problem in such networks is to be able to constrain the quantity of data admitted into the network in order to provide a good level of overall service. One solution to this problem is to allow a source to introduce a series of packets of data into the network only after a request to do so has been accepted by the network (in a step referred to as a “call acceptance”). In current networks, the decision whether or not to accept such a request is either made without considering the ability of the network to provide actual end-to-end requirements of the request or involves a centralised process that keeps track of the current set of requests accepted by the network as a whole. In the first case no guarantees of service can be offered by the network, only promises to treat some packets relatively better than others; while in the second case the centralised process limits the call-acceptance performance of the network. In any event, in current networks guarantees of service can only be given on the condition of substantial under-utilisation of the network resources, to provide capacity for use by guaranteed quality services.
When a switch in a network is running at or close to its full capacity, performance deteriorates for all traffic (i.e. the flow of packets of data as previously mentioned), unless some of the traffic is treated preferentially. Traditionally, congestion control mechanisms are introduced to manage traffic at the point when a queue at a switch starts to become full. Adding more buffers can apparently control loss. There is a penalty for this because the additional buffers introduce further delays and can lead to retransmission of traffic, and this then increases the congestion even more.
It is currently commonly understood in the academic literature as exemplified by Kleinrock, L. “Queuing Systems Volume 11: Computer Applications”, Wiley, New York, 1976 or Stallings, W, “High-Speed Networks: TCP/IP and ATM Design Principles”, Prentice Hall, N.J., 1998 (both of which are hereby incorporated by reference) that as the demand at any switch approaches unity then the average queue size and delay grow without bound and this is true however switches are managed and whatever their configuration. Traditionally, congestion control mechanisms as described in Jain, R., “Congestion Control and Traffic Management in ATM Networks: Recent Advances and A Survey”, Computer Networks and ISDN Systems, vol. 28, no 13, November 1996, pp1723–1738, are introduced to manage traffic at the point when the queue at a switch starts to become full. Adding more buffers can apparently control loss. There is a penalty for this because the additional buffers introduce further delays and can lead to retransmission of traffic, and this then increases the congestion even more.
There is a need to address these problems so as to be able to route transmissions with the possibility of improved service quality.
The use of priority or weighted fair queuing is known, as is the use of selective discard to limit queue length, as described for instance in McDysan, D. and Spohn, D. “ATM Theory and Application”, McGraw-Hill, New York 1998 pp 630–632. However there is no simple method currently described for deciding whether to admit a call considering both its loss and delay requirements exploiting the flexibility offered by the combination of these techniques.
WO 98/28939 describes a deterministic technique by which traffic is dynamically classified at a node and delivered downstream. Transfers can be aborted due to delay tolerance being exceeded. By this means, a certain number of flows are guaranteed a minimum bandwidth. However, only performance at a single node is addressed, not end-to-end performance. Furthermore, traffic is put into classes by the system, not on the basis of a user's decision.
U.S. Pat. No. 5,408,465 describes a system that offers soft deterministic guarantees that the end-to-end QoS (quality of service) is respected most of the time, and uses “pseudo-traffic” to decide whether to admit real traffic
U.S. Pat. No. 5,357,507 describes a system in which cell loss is the primary QoS parameter, relying on second derivatives of the input traffic stream characteristics. The system has 0 buffers. WO 95/17061 describes a system in which cell loss is the primary QoS parameter, and which uses large-deviation theory. EP 0 673 138 A describes a deterministic system in which cell loss is the primary QoS parameter. EP 0 814 632 A describes a system in which cell loss is the primary QoS parameter, and which assumes strict priority queuing. U.S. Ser. No. 08/723,649 and equivalents describe a system in which cell loss or delay is the QoS parameter. None of these systems considers both loss and delay in their QoS decision-making.
EP 0 828 362 A describes a system that uses a central network controller for CAC (call admission control), and does not provide guarantees for the duration of a connection.